#include <stdio.h>
#include <stdlib.h>

#define SIZE 9

// 链表结构
typedef struct LinkNode {
    int key;
    struct LinkNode* next;
}* LinkNode;

// 数组模拟哈希表
typedef struct HashTable {
    struct LinkNode* node;
}* HashTable;

int hash(int key) {
    return key % SIZE;
}

void init(HashTable hashTable) {
    hashTable->node = malloc(sizeof(struct LinkNode) * SIZE);
    // 将哈希表中的所有头节点初始化
    for (int i = 0; i < SIZE; ++i) {
        // hashtable->node[i] 指的是数组中第 i 个的 struct LinkNode 节点，而不是指针（地址），故后面是用 . 来引出其结构体变量
        hashTable->node[i].key = -1;
        hashTable->node[i].next = NULL;
    }
}

LinkNode createNode(int key) {
    LinkNode node = malloc(sizeof(struct LinkNode));
    node->key = key;
    node->next = NULL;
    return node;
}

void put(HashTable hashTable, int key) {
    int hashCode = hash(key);
    LinkNode head = &hashTable->node[hashCode];
    // 若已有元素占领该位置，则继续直至链表尾，然后插入
    while(head->next) {
        head = head->next;
    }
    head->next = createNode(key);
}

int get(HashTable hashTable, int key) {
    int hashCode = hash(key);
    LinkNode head = &hashTable->node[hashCode];
    while(head->next) {
        if(head->next->key == key) {
            return 1;
        }
        head = head->next;
    }
    return 0;
}

int main() {
    struct HashTable table;
    init(&table);

    put(&table, 10);
    put(&table, 19);
    put(&table, 20);

    printf("%d\n", get(&table, 20));
    printf("%d\n", get(&table, 17));
    printf("%d\n", get(&table, 19));
}